{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- Linux多线程服务端编程:使用muduo C++网络库 : 第12章"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 异或交换的误区与推荐做法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 关键观点整理"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "“异或交换”并不高效\n",
    "\n",
    "- 传统写法使用临时变量 (`tmp`) 交换字符，逻辑清晰、操作少、易于编译器优化。\n",
    "- “不用临时变量”的异或写法在现代体系结构上更慢：更多内存读写与指令依赖，无法并行。\n",
    "- 省去的临时变量几乎必定放在寄存器里，不会节省可观内存。\n",
    "- 组合成一行的“连写异或”会触发 C/C++ 未定义行为（因违反序列点/多次修改同一变量）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "STL `std::reverse` 完全可以放心使用\n",
    "\n",
    "- 对简单函数调用，现代编译器会自动内联展开，生成的机器码与手写循环同样高效。\n",
    "- 代码语义明确，复用性和可读性更高。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "切勿“想当然”地优化\n",
    "\n",
    "- 需要通过基准测试验证假设，而非臆测。\n",
    "- 查看汇编可帮助理解编译器生成的具体实现，但应认识到不同编译器/平台结果会变。\n",
    "- 真正的性能提升来自合适的算法和明确意图，编译器已经掌握大量微优化技巧（如用乘法替代除法）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 合理写法与危险写法对比\n",
    "\n",
    "| 编号 | 写法                   | 特点与结论                        |\n",
    "| ---- | ---------------------- | --------------------------------- |\n",
    "| V1   | 临时变量交换           | 简洁、两读两写、寄存器驻留        |\n",
    "| V2   | 三次异或交换           | 六读三写三异或，指令串联不可并行  |\n",
    "| V3   | `std::reverse`         | 表意清晰，通常会被内联，性能同 V1 |\n",
    "| V2b  | `*a ^= *b ^= *a ^= *b` | 未定义行为，禁止使用              |"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "! g++ -O3 benchmark_reverse.cpp -lbenchmark -lpthread -o benchmark_reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T07:32:48+08:00\n",
      "Running ./benchmark_reverse\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.13, 0.10, 0.09\n",
      "-----------------------------------------------------------------------------\n",
      "Benchmark                   Time             CPU   Iterations UserCounters...\n",
      "-----------------------------------------------------------------------------\n",
      "BM_reverse_by_swap    1348627 ns      1348935 ns          598 bytes_per_second=3.53492G/s items_per_second=3.70663M/s\n",
      "BM_reverse_by_xor     2028876 ns      2028941 ns          362 bytes_per_second=2.35018G/s items_per_second=2.46434M/s\n",
      "BM_reverse_by_std     1440841 ns      1440970 ns          482 bytes_per_second=3.30914G/s items_per_second=3.46988M/s\n"
     ]
    }
   ],
   "source": [
    "! ./benchmark_reverse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "2025-10-10T07:32:58+08:00\n",
      "Running ./benchmark_reverse\n",
      "Run on (16 X 3792.92 MHz CPU s)\n",
      "CPU Caches:\n",
      "  L1 Data 32 KiB (x8)\n",
      "  L1 Instruction 32 KiB (x8)\n",
      "  L2 Unified 1024 KiB (x8)\n",
      "  L3 Unified 16384 KiB (x1)\n",
      "Load Average: 0.18, 0.12, 0.09\n",
      "------------------------------------------------------------------------------------\n",
      "Benchmark                          Time             CPU   Iterations UserCounters...\n",
      "------------------------------------------------------------------------------------\n",
      "BM_reverse_by_swap_mean      1307601 ns      1307204 ns            5 bytes_per_second=3.64983G/s items_per_second=3.82712M/s\n",
      "BM_reverse_by_swap_median    1293851 ns      1294015 ns            5 bytes_per_second=3.68494G/s items_per_second=3.86394M/s\n",
      "BM_reverse_by_swap_stddev      35792 ns        34879 ns            5 bytes_per_second=98.9674M/s items_per_second=101.343k/s\n",
      "BM_reverse_by_swap_cv           2.74 %          2.67 %             5 bytes_per_second=2.65% items_per_second=2.65%\n",
      "BM_reverse_by_xor_mean       2039532 ns      2038787 ns            5 bytes_per_second=2.34468G/s items_per_second=2.45858M/s\n",
      "BM_reverse_by_xor_median     2091229 ns      2091359 ns            5 bytes_per_second=2.28003G/s items_per_second=2.39079M/s\n",
      "BM_reverse_by_xor_stddev      113874 ns       112486 ns            5 bytes_per_second=135.934M/s items_per_second=139.197k/s\n",
      "BM_reverse_by_xor_cv            5.58 %          5.52 %             5 bytes_per_second=5.66% items_per_second=5.66%\n",
      "BM_reverse_by_std_mean       1394342 ns      1394398 ns            5 bytes_per_second=3.42011G/s items_per_second=3.58624M/s\n",
      "BM_reverse_by_std_median     1389712 ns      1389891 ns            5 bytes_per_second=3.43075G/s items_per_second=3.5974M/s\n",
      "BM_reverse_by_std_stddev       17867 ns        17787 ns            5 bytes_per_second=44.7018M/s items_per_second=45.7747k/s\n",
      "BM_reverse_by_std_cv            1.28 %          1.28 %             5 bytes_per_second=1.28% items_per_second=1.28%\n"
     ]
    }
   ],
   "source": [
    "! ./benchmark_reverse --benchmark_repetitions=5 --benchmark_report_aggregates_only=true"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- reverse_by_swap: https://godbolt.org/z/94xjExMjz"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "reverse_by_swap(char*, int):\n",
    "        movsx   rsi, esi\n",
    "        lea     rax, [rdi-1+rsi]\n",
    "        cmp     rdi, rax\n",
    "        jnb     .L1\n",
    ".L3:\n",
    "        movzx   edx, BYTE PTR [rdi]\n",
    "        movzx   ecx, BYTE PTR [rax]\n",
    "        add     rdi, 1\n",
    "        sub     rax, 1\n",
    "        mov     BYTE PTR [rdi-1], cl\n",
    "        mov     BYTE PTR [rax+1], dl\n",
    "        cmp     rdi, rax\n",
    "        jb      .L3\n",
    ".L1:\n",
    "        ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- reverse_by_xor: https://godbolt.org/z/Ph7EKvTEf"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "reverse_by_xor(char*, unsigned long):\n",
    "        lea     rdx, [rdi-1+rsi]\n",
    "        cmp     rdi, rdx\n",
    "        jnb     .L1\n",
    ".L3:\n",
    "        movzx   eax, BYTE PTR [rdi]\n",
    "        xor     al, BYTE PTR [rdx]\n",
    "        sub     rdx, 1\n",
    "        mov     BYTE PTR [rdi], al\n",
    "        xor     al, BYTE PTR [rdx+1]\n",
    "        mov     BYTE PTR [rdx+1], al\n",
    "        xor     BYTE PTR [rdi], al\n",
    "        add     rdi, 1\n",
    "        cmp     rdi, rdx\n",
    "        jb      .L3\n",
    ".L1:\n",
    "        ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- reverse_by_std: https://godbolt.org/z/9381jszvx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "vscode": {
     "languageId": "shellscript"
    }
   },
   "outputs": [],
   "source": [
    "reverse_by_std(char*, unsigned long):\n",
    "        add     rsi, rdi\n",
    "        cmp     rsi, rdi\n",
    "        jne     .L5\n",
    "        ret\n",
    ".L3:\n",
    "        movzx   eax, BYTE PTR [rdi]\n",
    "        movzx   edx, BYTE PTR [rsi]\n",
    "        add     rdi, 1\n",
    "        mov     BYTE PTR [rdi-1], dl\n",
    "        mov     BYTE PTR [rsi], al\n",
    ".L5:\n",
    "        sub     rsi, 1\n",
    "        cmp     rdi, rsi\n",
    "        jb      .L3\n",
    "        ret"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "C++17",
   "language": "C++17",
   "name": "xcpp17"
  },
  "language_info": {
   "codemirror_mode": "text/x-c++src",
   "file_extension": ".cpp",
   "mimetype": "text/x-c++src",
   "name": "c++",
   "version": "17"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
